/**
 * \file List.c
 * \brief Implémentation d'une liste générique basée sur le type (void *)
 * 
 * \author Franck Séhédic (franck.sehedic@ecole.ensicaen.fr)
 * 
 * \version 0.1
 * 
 * \date 25-11-2007
 */
#include "List.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#ifndef NULL
#define NULL (void *)0
#endif

#define max(a,b) (((a)>(b))?(a):(b))

/**
 * \struct _ListTab
 * \brief Tableau doublement chainé représentant une partie d'une liste
 */
typedef struct _ListTab{
	void** data;			/*< pointeur sur les données appartenant à ce tableau */
	struct _ListTab* next;	/*< pointeur sur le tableau suivant */
	struct _ListTab* prev;	/*< pointeur sur le tableau précédent */
	int size;				/*< Nombre d'élements actuellement dans ce tableau */
} ListTab;

/**
 * \struct _List
 * \brief Représente la structure interne d'une liste */
struct _List {
	ListTab* first;			/*< pointeur sur le premier tableau de cette liste */
	ListTab* last;			/*< pointeur sur le dernier tableau de cette liste */
	ListTab* current;		/*< pointeur sur le tableau actuellement utilisé lors du parcours de la liste */
	int pos;				/*< position actuelle, relative au tableau "current", utilisé lors du parcours de la liste */
	unsigned int size;		/*< Nombre d'éléments total dans la liste */
	unsigned int tabSize;	/*< Nombre d'éléments maximum par tableau dans cette liste */
};

void listDebugTabList(ListTab* t){
	int i;
	printf("%.8X | %.8X | %.8X | %.8X | %2d\n", \
			(unsigned int)t,\
			(unsigned int)t->data,\
			(unsigned int)t->next,\
			(unsigned int)t->prev,\
			t->size);
	for(i = 0; i < t->size ;i++){
		printf("%.8X ",(unsigned int)t->data[i]);
	}
	printf("\n");
}
void listDebug(List* list){
	ListTab* t;
	int i,j;
	
	printf("================\n");
	printf("list : 0x%.8X\n",(unsigned int)list);
	if(list == NULL) return;
	
	printf("current  | first    | last     | pos | size |  tabSize\n");
	printf("%.8X | %.8X | %.8X | %3d | %4d | %2d\n",
			(unsigned int)list->current, \
			(unsigned int)list->first, \
			(unsigned int)list->last, \
			  list->pos, \
			  list->size, \
			  list->tabSize); 
	
	if((t = list->first) != NULL){
		j = 0;
		printf("     | &tab     | data     | next     | prev     |  size\n");
		while(t != NULL){
			printf("[%2d] | %.8X | %.8X | %.8X | %.8X | %2d\n",j++,\
					(unsigned int)t,\
					(unsigned int)t->data,\
					(unsigned int)t->next,\
					(unsigned int)t->prev,\
					t->size);
			for(i = 0; i < t->size ;i++){
				printf("%.8X ",(unsigned int)t->data[i]);
			}
			printf("\n");
			t = t->next;
		}
	}
	
	printf("================\n");
}

/**
 * \fn void listTabRemove(List* l,ListTab* t)
 * \brief Supprime un tableau de la liste
 * 
 * \param[in] l liste
 * \param[in] t Tableau à supprimer
 */
void listTabRemove(List* l,ListTab* t){
	
	if(t->next == NULL && t->prev == NULL) return;
	
	if(t->next == NULL) l->last = t->prev;
	else 				t->next->prev = t->prev;
	
	if(t->prev == NULL) l->first = t->next;
	else t->prev->next = t->next;
	
	free(t->data);
	free(t);
}

/**
 * \fn void listTabMerge(List* l,ListTab* t)
 * \brief Fusionne t avec le tableau suivant
 * \note Attention on doit avoir les précondition suivantes :
 * t->next != NULL 
 * ET
 * t->size + t->next->size < l->tabSize
 * 
 * t
 * A A 0 0 0
 * 
 * t->next
 * B B 0 0 0
 * 
 * => listTabMerge(l,t)
 * A A B B 0
 * 
 * \param[in] l Liste
 * \param[in] t Tableau qui va être fusionné avec le tableau suivant
 */
void listTabMerge(List* l,ListTab* t){
	ListTab* tNext;
	
	tNext = t->next;
	
	memcpy(t->data + t->size,tNext->data,tNext->size * sizeof(void*));
	t->size += tNext->size;
	listDebug(l);
	
	/*
	 * On supprime tNext, mais on utilise pas listTabRemove
	 * car pas optimisé
	 */
	t->next = tNext->next;
	
	if(tNext->next == NULL) l->last = t;
	else t->next->prev = t;
	

	free(tNext->data);
	free(tNext);
}

/**
 * \fn void listSplitTab(List* list,ListTab* listTab)
 * \brief Sépare un tableau en 2 tableau de même taille
 *        tout en gardant l'ordre des élements.
 * 
 * \param[in] list Liste
 * \param[in] listTab Tableau à séparer en 2
 */
void listSplitTab(List* list,ListTab* listTab){
	ListTab* newListTab;
	unsigned int newsize;
	
	newListTab = malloc(sizeof(ListTab));
	newListTab->size = 0;
	newListTab->data = malloc(list->tabSize * sizeof(void*));

	
	newListTab->next = listTab->next;
	newListTab->prev = listTab;
	
	if(newListTab->next != NULL) newListTab->next->prev = newListTab;
	listTab->next = newListTab;
	
	newsize = listTab->size/2;
	memcpy(newListTab->data,listTab->data + listTab->size - newsize,newsize * sizeof(void*));
	
	newListTab->size = newsize;
	listTab->size -= newsize;
	
	if(list->last == listTab) list->last = newListTab;
}

/**
 * \fn void* listRemove(List* list,int relPos,ListTab* t)
 * \brief Enlève un élement d'une liste en fonction de sa position relative
 * 
 * \param[in] list liste
 * \param[in] relPos Position relative de l'élement
 * \param[in] listTab Tableau dans lequel se trouve la position
 */
void* listRemove(List* list,int relPos,ListTab* t){
	void* delElm;
	
	if(relPos > t->size) return NULL;
	
	delElm = t->data[relPos];
	
	memmove(t->data + relPos,t->data + (relPos + 1),(t->size - relPos + 1) * sizeof(void*));

	list->size--;
	t->size--;

	if(t->size == 0)
		listTabRemove(list,t); /* delete it if unused */
	else if ( t->next && ((t->next->size + t->size) < (int)list->tabSize))
		listTabMerge(list,t); /* merge it with next tab if possible */
	else if ( t->prev && ((t->prev->size + t->size) < (int)list->tabSize)){
		listDebug(list);
		listTabMerge(list,t->prev); /* merge it with previous tab if possible */
	}
		
	
	
	return delElm;
}

/**
 * \fn void listInsert(List* list,int relPos,ListTab* listTab,void* elm)
 * \brief Insert un élement dans une liste 
 *        en fonction de son tableau et de sa position relative
 * 
 * \param[in] list liste
 * \param[in] relPos position relative à listTab
 * \param[in] listTab tableau dans lequel se trouve la position demandée
 * \param[in] elm Element à insérer dans la liste
 */
void listInsert(List* list,int relPos,ListTab* listTab,void* elm){
	
	if(relPos < listTab->size){
		memmove(listTab->data + relPos + 1,listTab->data + relPos,(listTab->size - relPos) * sizeof(void*));
	}
		
	/* on insère l'élement dans le tableau */
	listTab->data[relPos] = elm;
	listTab->size++;
	
	/* /!\ important! si le tableau est plein on le split */
	if(listTab->size == (int)list->tabSize)
		listSplitTab(list,listTab);
	
	list->size++;
}

/**
 * \fn unsigned int listGetRelativeNewPos(List* list,unsigned int pos,ListTab** listTab)
 * \brief Traduit une position absolue en une position relative.
 * 	Cette position relative est la seule utilisable dans notre tad.
 *  La position est une position encore inutilisée et donc vide dans un des tab.
 * 
 * \param[in] list liste
 * \param[in] pos position absolue
 * 
 * \param[out] listTab tableau dans lequel se trouve la position demandée
 * \return position relative au tableau retourné dans listTab
 */
unsigned int listGetRelativeNewPos(List* list,unsigned int pos,ListTab** listTab){
	ListTab* tab;
	unsigned int curPos;
	
	if(pos > list->size){
		listTab = NULL;
		return 0;
	}
	
	if(pos <= list->size/2){
		/* on parcours en avant la liste */
		tab = list->first;
		curPos = 0;
		while(pos > curPos + tab->size){
			curPos += tab->size;
			tab = tab->next;
		}
	}else {
		/* on parcours en arrière la liste*/
		tab = list->last;
		curPos = list->size - tab->size;
		while(pos <= curPos){
			curPos -= tab->size;
			tab = tab->prev;
		}
	}
	*listTab = tab;
	return pos - curPos;	
}

/**
 * \fn int listGetRelativePos(List* list,unsigned int pos,ListTab** listTab)
 * \brief Traduit une position absolue en une position relative.
 * 	Cette position relative est la seule utilisable dans notre tad.
 * 
 * \param[in] list liste
 * \param[in] pos position absolue
 * 
 * \param[out] listTab tableau dans lequel se trouve la position demandée
 * \return Position relative au tableau retourné dans listTab
 *  Si erreur : pos = -1, listTab = NULL
 */
int listGetRelativePos(List* list,unsigned int pos,ListTab** listTab){
	ListTab* tab;
	unsigned int curPos;
	
	if(pos >= list->size){
		listTab = NULL;
		return -1;
	}
	
	if(pos < list->size/2){
		/* on parcours en avant la liste */
		tab = list->first;
		curPos = 0;
		while(pos >= curPos + tab->size){
			curPos += tab->size;
			tab = tab->next;
		}
	}else {
		
		/* on parcours en arrière la liste*/
		tab = list->last;
		curPos = list->size - tab->size;
		while(pos < curPos){
			curPos -= tab->size;
			tab = tab->prev;
		}
	}
	*listTab = tab;
	return pos - curPos;	
}

/**
 * \fn List* createList(unsigned int tabSize)
 * \brief Créer une liste
 * 
 * \param[in] tabSize Taille utilisée pour les tableaux
 * 
 * \return Nouvelle liste vide
 */
List* createList(unsigned int tabSize) {
	List* newList;
	ListTab* listTab;
	
	newList = malloc(sizeof(List));
	newList->current = NULL;
	newList->pos = 0;
	newList->size = 0;
	newList->tabSize = tabSize;
	
	listTab = malloc(sizeof(ListTab));
	listTab->data = malloc(tabSize * sizeof(void*));
	listTab->next = NULL;
	listTab->prev = NULL;
	listTab->size = 0;
	
	newList->first = listTab;
	newList->last = listTab;
	
	return newList;
}
/**
 * \fn List* newList()
 * \brief Créer une liste
 * 
 * \return Nouvelle liste vide
 */
#define DEFAULT_TAB_SIZE 5
List* newList(){
	return createList(DEFAULT_TAB_SIZE);
}

/**
 * \fn void deleteList(List* list)
 * \brief Supprime une liste
 * 
 * \param[in] list Liste
 */
void deleteList(List* list) {
	ListTab *curTab,*nextTab;
	
	assert(list != NULL);
	
	curTab = list->first;
	while(curTab != NULL) {
		free(curTab->data);
		nextTab = curTab->next;
		free(curTab);
		curTab = nextTab;
	}
}

/**
 * \fn int listIsEmpty(List* list)
 * \brief regarde si la liste est vide
 * 
 * \param[in] list Liste
 * 
 * \return 1 si la liste est vide, 0 sinon
 */
int listIsEmpty(List* list){
	assert(list != NULL);
	
	return (list->size == 0);
}

/**
 * \fn int listGetSize(List* list)
 * \brief Retourne la taille d'une liste
 * 
 * \param[in] list Liste
 * 
 * \return Nombre d'éléments dans la liste
 */
int listGetSize(List* list) {
	assert(list != NULL);
	
	return list->size;
}

/**
 * \fn int listInsertAt(List* list,void* elm,unsigned int pos)
 * \brief Insert un élément à une position donnée
 * 
 * \param[in] list Liste
 * \param[in] elm Element à insérer
 * \param[in] pos Position à laquelle insérer l'élement
 * 
 * \return 1 si tout s'est bien passé, 0 sinon
 */
int listInsertAt(List* list,void* elm,unsigned int pos){
	ListTab* listTab;
	int relPos;
	int i;
	
	assert(list != NULL);
	assert(elm != NULL);
	
	if(pos > list->size) return 0;
	
	/* on cherche une nouvelle position libre */
	relPos = listGetRelativeNewPos(list,pos,&listTab);
	if(listTab == NULL) return 0;
	
	/* on décale le tableau pour insérer l'élement */
	for(i = relPos; i < listTab->size ; i++){
		listTab->data[i] = listTab->data[i+1];
	}
	
	listInsert(list,relPos,listTab,elm);

	return 1;
}

/**
 * \fn void listInsertFirst(List* list,void* elm)
 * \brief Insert un élément en début de liste
 * 
 * \param[in] list Liste
 * \param[in] elm Element à insérer
 */
void listInsertFirst(List* list,void* elm){
	ListTab* listTab;
	int relPos;
	
	assert(list != NULL);
	assert(elm != NULL);
	
	listTab = list->first;
	relPos = 0;
	
	listInsert(list,relPos,listTab,elm);
}

/**
 * \fn void listInsertLast(List* list,void* elm)
 * \brief Insert un élément à la fin de la liste
 * 
 * \param[in] list Liste
 * \param[in] elm Element à insérer
 */
void listInsertLast(List* list,void* elm){
	ListTab* listTab;
	int relPos;
	
	assert(list != NULL);
	assert(elm != NULL);
	
	listTab = list->last;
	relPos = listTab->size;
	
	listInsert(list,relPos,listTab,elm);
}

/**
 * \fn void* listGetAt(List* list,unsigned int pos)
 * \brief Retourne l'élement situé à la position pos
 * 
 * \param[in] list Liste
 * \param[in] pos Position de l'élement voulu
 * 
 * \return L'élement situé à la position pos
 */
void* listGetAt(List* list,unsigned int pos) {
	ListTab* listTab;
	int relPos;
	
	assert(list != NULL);
	
	if(pos >= list->size) return NULL;
	
	relPos = listGetRelativePos(list,pos,&listTab);

	if(relPos == -1) return NULL;
	
	/* Gestion de l'itération */
	list->current = listTab;
	list->pos = relPos;
	
	return listTab->data[relPos];
}

/**
 * \fn void* listGetFirst(List* list)
 * \brief Retourne le premier élement de la liste
 * 
 * \param[in] list Liste
 * 
 * \return L'élement situé au début de la liste
 */
void* listGetFirst(List* list){
	assert(list != NULL);
	
	if(list->size == 0) return NULL;
	
	/* Gestion de l'itération */
	list->current = list->first;
	list->pos = 0;
	
	return list->current->data[list->pos];
}

/**
 * \fn void* listGetLast(List* list)
 * \brief Retourne le dernier élement de la liste
 * 
 * \param[in] list Liste
 * 
 * \return L'élement situé à la fin de la liste
 */
void* listGetLast(List* list){
	assert(list != NULL);
	
	if(list->size == 0) return NULL;
	
	/* Gestion de l'itération */
	list->current = list->last;
	list->pos = list->current->size - 1;
	
	
	return list->current->data[list->pos];
}

/**
 * \fn void* listGetNext(List* list)
 * \brief Retourne le prochaine élement de la liste
 * /!\ l'itération doit être initialisé par un appel à 
 *   - listGetFirst
 *   - listGetLast
 *   - listGet
 * \param[in] list Liste
 * 
 * \return Le prochain élément de la liste
 *  NULL si il n'y a plus d'autre élement ou si l'itération n'a pas était initialisée
 */
void* listGetNext(List* list){
	assert(list != NULL);

	if(list->current == NULL) return NULL;
	
	if(++(list->pos) == list->current->size){
		list->current = list->current->next;
		if(list->current == NULL) return NULL;
		
		list->pos = 0;
	}
	
	return list->current->data[list->pos];
}

/**
 * \fn void* listGetPrev(List* list)
 * \brief Retourne le prochaine élement de la liste
 * /!\ l'itération doit être initialisé par un appel à 
 *   - listGetFirst
 *   - listGetLast
 *   - listGet
 * \param[in] list Liste
 * 
 * \return L'élément précédent de la liste
 *  NULL si il n'y a plus d'autre élement ou si l'itération n'a pas était initialisée
 */
void* listGetPrev(List* list){
	assert(list != NULL);
	
	if(list->current == NULL) return NULL;
	
	if(--(list->pos) < 0){
		list->current = list->current->prev;
		if(list->current == NULL) return NULL;
		
		list->pos = list->current->size -1;
	}
	
	return list->current->data[list->pos];
}

/**
 * \fn void* listRemAt(List* list, unsigned int pos)
 * \brief Enlève l'élement situé à la position pos de la liste
 * 
 * \param[in, out] list Liste
 * \param[in] pos Position de l'élement à enlever
 * 
 * \return L'élément enlevé
 *  NULL si la position est invalide
 */
void* listRemAt(List* list, unsigned int pos){
	ListTab* listTab;
	int relPos;
	
	assert(list != NULL);
	
	if(pos > list->size) return NULL;
	
	/* on cherche une la position relative */
	relPos = listGetRelativePos(list,pos,&listTab);
	if(relPos == -1) return NULL;
	
	return listRemove(list,relPos,listTab);
}

/**
 * \fn void* listRemFirst(List* list)
 * \brief Enlève l'élément situé au début de la liste
 * 
 * \param[in, out] list Liste
 * 
 * \return L'élément qui était situé au début de la liste
 *  NULL si la liste est vide
 */
void* listRemFirst(List* list){
	assert(list != NULL);
	
	if(listIsEmpty(list)) return NULL;
	return listRemove(list,0,list->first);
}

/**
 * \fn void* listRemLast(List* list)
 * \brief Enlève l'élement situé en fin de liste
 * 
 * \param[in, out] list Liste
 * 
 * \return L'élément qui était situé en fin de liste
 *  NULL si la liste est vide
 */
void* listRemLast(List* list){
	assert(list != NULL);
	
	if(listIsEmpty(list)) return NULL;
	return listRemove(list,list->last->size - 1,list->last);
}

/**
 * \fn void* listRem(List* list,void* elm)
 * \brief Enlève l'élement elm de la liste
 * 
 * \param[in, out] list Liste
 * \param[in] elm Element à enlever de la liste
 * 
 * \return L'élément qui a été enlevé de la liste
 *  NULL si elm n'est pas présent dans la liste
 * 
 * \bug Cette primitive peut être lente
 *      étant donné qu'elle entraine un parcours complet de la liste.
 */
void* listRem(List* list,void* elm){
	ListTab* t;
	int i;
	
	assert(list != NULL);
	assert(elm != NULL);
	
	if(listIsEmpty(list)) return NULL;
	
	/* on parcours la liste */
	t = list->first;
	i = 0;
	while(t != NULL && elm != t->data[i++]){
		if(i == t->size){
			i = 0;
			t = t->next;
		}
	}
	if(t == NULL) return NULL;
	
	return listRemove(list,i,t);
}

/**
 * \fn void* listReplaceAt(List* list,void* elm,unsigned int pos)
 * \brief Remplace l'élément sité en position pos, par l'élément elm
 * 
 * \param[in, out] list Liste
 * \param[in] elm Element à insérer dans la liste
 * \param[in] pos Position de l'élément à enlever de la liste
 * 
 * \return L'élément qui a été enlevé de la liste
 *  NULL si il n'y a pas d'élément en position pos
 */
void* listReplaceAt(List* list,void* elm,unsigned int pos){
	ListTab* listTab;
	int relPos;
	void* oldElm;
	
	assert(list != NULL);
	assert(elm != NULL);
	
	if(pos >= list->size) return NULL;
	
	relPos = listGetRelativePos(list,pos,&listTab);
	if(relPos == -1) return NULL;
	
	oldElm = listTab->data[relPos];
	listTab->data[relPos] = elm;
	
	return oldElm;
}

/**
 * \fn void* listReplace(List* list,void* elmNew,void* elmOld)
 * \brief Remplace l'élément elmOld par l'élément elmNew
 * 
 * \param[in, out] list Liste
 * \param[in] elmNew Element à insérer dans la liste
 * \param[in] elmOld Element à enlever de la liste
 * 
 * \return L'élément qui a été enlevé de la liste
 *  NULL si elmOld n'est pas présent dans la liste
 * 
 * \bug Cette primitive peut être lente
 *      étant donné qu'elle entraine un parcours complet de la liste.
 */
void* listReplace(List* list,void* elmNew,void* elmOld){
	ListTab* t;
	int i;
	
	assert(list != NULL);
	assert(elmNew != NULL);
	assert(elmOld != NULL);
	
	if(listIsEmpty(list)) return NULL;
	
	/* on parcours la liste */
	t = list->first;
	i = 0;
	while(t != NULL && elmOld != t->data[i++]){
		if(i == t->size){
			i = 0;
			t = t->next;
		}
	}
	if(t == NULL) return NULL;
	
	t->data[i] = elmNew;
	
	return elmOld;
}

/**
 * \fn int listSwitch(List* list, unsigned int posA, unsigned int posB)
 * \brief Echange l'élément sité en position posA avec l'élément sité en position posB
 * 
 * \param[in, out] list Liste
 * \param[in] posA Position du premier élément
 * \param[in] posB Position du second élément
 * 
 * \return 1 si l'échange a eu lieu, 0 sinon (un des élément n'a pas été trouvé à la position demandée)
 */
int listSwitch(List* list, unsigned int posA, unsigned int posB){
	int relPosA,relPosB;
	ListTab *listTabA,*listTabB;
	void* elm;
	
	assert(list != NULL);
	
	if(posA == posB) return 1;
	
	relPosA = listGetRelativePos(list,posA,&listTabA);
	if(relPosA == -1) return 0;
	relPosB = listGetRelativePos(list,posB,&listTabB);
	if(relPosB == -1) return 0;
	
	elm = listTabA->data[relPosA];
	listTabA->data[relPosA] = listTabB->data[relPosB];
	listTabB->data[relPosB] = elm;
	
	return 1;	
}

/**
 * \fn unsigned int listPosOf(List* list,void* elm)
 * \brief Retourne la position de l'élément elm dans la liste
 * 
 * \param[in, out] list Liste
 * \param[in] elm Element à recherche dans la liste
 * 
 * \return La position de l'élément recherché
 *  -1 si elm n'est pas présent dans la liste
 * 
 * \bug Cette primitive peut être lente
 *      étant donné qu'elle entraine un parcours complet de la liste.
 * 
 * \bug La valeur de retour -1 n'est pas représentable par le type unsigned int.
 *      la valeur retournée en cas d'erreur est en fait (UINT_MAX).
 */
unsigned int listPosOf(List* list,void* elm){
	ListTab* t;
	int i;
	unsigned int absPos;
	
	assert(list != NULL);
	assert(elm != NULL);
	
	if(listIsEmpty(list)) return LIST_INVALIDPOS;
	
	/* On parcours la liste */
	t = list->first;
	i = 0;
	absPos = 0;
	while(t != NULL && elm != t->data[i++]){
		if(i == t->size){
			absPos += t->size;
			i = 0;
			t = t->next;
		}
	}
	if(t == NULL) return LIST_INVALIDPOS;
	absPos += i - 1;
	
	return absPos;
}


/* Itererators */
struct _ListIterator{
	ListTab* current;
	int pos;
	List* list;
};

void listItReset(ListIterator* it){
	assert(it != NULL);
	assert(it->list != NULL);
	
	if(it == NULL || it->list == NULL) return;
	
	it->current = it->list->first;
	it->pos = 0;
}

void* newListIt(List* l){
	ListIterator* it;
	
	assert(l != NULL);
	
	if(l == NULL) return NULL;
	
	it = malloc(sizeof(ListIterator));
	if(it == NULL) return NULL;
	
	it->list = l;
	listItReset(it);
	
	return it;
}



void deleteListIt(ListIterator* it){
	assert(it != NULL);

	free(it);
}

void* listItGetCurrent(ListIterator* it){
	assert(it != NULL);
	
	if(it == NULL || it->current == NULL) return NULL;

	return it->current->data[it->pos];
}

void* listItGetNext(ListIterator* it){
	assert(it != NULL);
	assert(it->list != NULL);
	
	if(it->current == NULL){
		it->current = it->list->first;
		it->pos = 0;
	}else if(++(it->pos) == it->current->size){
		it->current = it->current->next;
		if(it->current == NULL) return NULL;
		it->pos = 0;
	}
	
	return listItGetCurrent(it);
}

void* listItGetPrev(ListIterator* it){
	assert(it != NULL);
	assert(it->list != NULL);
	
	if(it->current == NULL){
		it->current = it->list->last;
		it->pos = it->current->size - 1;
	}else if(--(it->pos) < 0){
		it->current = it->current->prev;
		if(it->current == NULL) return NULL;
		it->pos = it->current->size - 1;
	}
	
	return listItGetCurrent(it);
}

